package leetcode.medium.limit100;

import leetcode.ListNode;

public class No86 {
    public static void main(String[] args) {
        ListNode byArray = ListNode.createByArray(new int[]{1, 4, 3, 2, 5, 2});
        No86 no86 = new No86();

        ListNode.print(no86.partition(byArray, 3));
    }

    public ListNode partition(ListNode head, int x) {
        ListNode newNode1 = new ListNode(-1);
        ListNode p1 = newNode1;
        ListNode newNode2 = new ListNode(-1);
        ListNode p2 = newNode2;
        ListNode p = head;
        while (p != null) {
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.next = p;
                p1 = p1.next;
            }
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        p1.next = newNode2.next;
        return newNode1.next;
    }
}
